class Solution
{
public:
    int maxKDivisibleComponents(int n, vector<vector<int>> &edges, vector<int> &values, int k)
    {
        vector<int> degree(n, 0);
        vector<vector<int>> graph(n);
        for (auto &edge : edges)
        {
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
            ++degree[edge[0]];
            ++degree[edge[1]];
        }
        ++degree[0];

        vector<int> parents(n, -1);
        function<void(int, int)> build = [&](int node, int parent)
        {
            parents[node] = parent;
            for (auto neighbor : graph[node])
            {
                if (neighbor != parent)
                {
                    build(neighbor, node);
                }
            }
        };
        build(0, -1);

        queue<int> q;
        for (int i = 0; i < n; ++i)
        {
            if (degree[i] == 1)
            {
                q.push(i);
            }
        }

        int result = 0;
        while (!q.empty())
        {
            int node = q.front();
            q.pop();

            int parent = parents[node];

            if (values[node] % k == 0)
            {
                ++result;
            }
            else
            {
                values[parent] += values[node];
                values[parent] %= k;
            }

            if (parent != -1)
            {
                --degree[parent];
                if (degree[parent] == 1)
                {
                    q.push(parent);
                }
            }
        }
        return result;
    }
};